/*
 * binary_tree.c
 *
 *  Created on: 2020��1��1��
 *      Author: Administrator
 */


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "../../include/tree/binary_tree.h"
#include "../../include/queue/linked_queue.h"
#include "../../include/stack/seq_stack.h"

void create_tree(BinTree* root) {

	char ch;
	scanf("%c", &ch);
	if (ch == '.') *root = NULL;
	else {
		*root = (BinTree) malloc(sizeof(BTNode));
		(*root)->data = ch;
		create_tree(&((*root)->left));
		create_tree(&((*root)->right));
	}
}

bool is_tree_empty(BinTree root) {
	if (root == NULL) {
		return true;
	}
	return false;
}

int count_nodes(BinTree root) {

	if (root == NULL) {
		return 0;
	} else {
		return count_nodes(root->left) + count_nodes(root->right) + 1;
	}
}

int height(BinTree root) {

	int left, right, max;
	if (root == NULL) {
		return 0;
	} else if (root->left == NULL && root->right == NULL) {
			return 1;
	} else {
		left = height(root->left);
		right = height(root->right);
		max = left > right? left : right;
		return 1 + max;
	}
}

void preorder(BinTree root) {

	if (root == NULL) {
		return;
	} else {
		printf("%c ", root->data);
		preorder(root->left);
		preorder(root->right);
	}
}

void inorder(BinTree root) {

	if (root == NULL) {
		return;
	} else {
		inorder(root->left);
		printf("%c ", root->data);
		inorder(root->right);
	}
}

void postorder(BinTree root) {

	if (root == NULL) {
		return;
	} else {
		postorder(root->left);
		postorder(root->right);
		printf("%c ", root->data);
	}
}

/**
 * 先序遍历非递归算法
 * 循环遍历当前结点，如果当前结点p不为空，就打印节点，节点入栈，访问左孩子；
 * 否则（即当前结点为空），返回上一结点，访问右孩子
 */
void unr_preorder(BinTree root) {

	if (root == NULL) return;

	BTNode* p = root;
	SeqStack* stack = (SeqStack*) malloc(sizeof(SeqStack));
	init_seqstack(stack);

	while (p != NULL || !is_empty_seqstack(stack)) {

		// 如果当前p不为空，就打印节点，节点入栈，访问左孩子
		if (p != NULL) {
			printf("%c ", p->data);
			push_seqstack(stack, (int)p);
			p = p->left;
		} else {
		// p为空时，返回上一结点，访问右孩子
			p = (BTNode*)pop_seqstack(stack);
			p = p->right;
		}
	}
}

/**
 * 中序遍历（迭代法）
 * 使用迭代法写中序遍历时，需要借用指针来帮助访问节点，栈用来处理节点上的元素
 * 当非递归遍历二叉树时，不再区分左、右子树的概念，只有当前节点。
 * 循环遍历当前结点，对于每个节点，若该节点不为空，就先访问左孩子；
 * 否则，返回上一节点，访问中间节点，访问右孩子
 */
void unr_inorder(BinTree root) {

	if (root == NULL) return;

	BTNode* p = root;
	SeqStack* stack = (SeqStack*) malloc(sizeof(SeqStack));
	init_seqstack(stack);

	// 遍历当前结点
	while (p != NULL || !is_empty_seqstack(stack)) {

		if (p != NULL) {  // 指针用来访问节点，访问到最底层
			push_seqstack(stack, (int)p);
			p = p->left;            // 访问左
		} else {
			p = (BTNode*)pop_seqstack(stack); // 返回上一节点
			printf("%c ", p->data); // 访问中
			p = p->right;           // 访问右
		}
	}
}

/**
 * 后序遍历的非递归算法
 * 什么时候打印当前结点？当左孩子为空时，并且右孩子为空或者已访问，则打印当前结点p
 * 因此，需要指针pre，指向上一已访问结点
 * 循环遍历当前结点，先处理左孩子，判断是否可以打印当前结点，不可以再处理右孩子。
 * 后序的流程，中序的思考：当左孩子为空时，返回上一结点。判断是否可以打印当前结点；否则，访问右孩子
 */
void unr_postorder(BinTree root) {

	if (root == NULL) return;

	BTNode* p = root;   // 当前结点
	BTNode* pre = NULL; // 上一已访问结点
	SeqStack* stack = (SeqStack*) malloc(sizeof(SeqStack));
	init_seqstack(stack);

	while (p != NULL || !is_empty_seqstack(stack)) {

		// 先处理左孩子
		while (p != NULL) {
			push_seqstack(stack, (int)p);
			p = p->left;
		}

		p = (BTNode*) peek_seqstack(stack); // 返回上一结点

		// 判断是否可以打印当前结点，否则访问右孩子
		if (p->right == NULL || p->right == pre) {
			// 如果当前结点右孩子为空，或者右孩子已访问，则打印
			printf("%c ", p->data);
			pop_seqstack(stack);
			pre = p;  // 设置当前结点p已访问
			p = NULL; // 不再重复关注当前结点
		} else {
			p = p->right;
		}
	}
}

void levelorder(BinTree root) {

	// 队列保存未访问节点
	LinkedQueue* queue = (LinkedQueue*)malloc(sizeof(LinkedQueue));
	init_queue(queue);

	enqueue(queue, (int)root);

	while (!is_queue_empty(queue)) {

		BTNode* root = (BTNode*)dequeue(queue);
		printf("%c ", root->data);
		if (root->left != NULL) {
			enqueue(queue, (int)root->left);
		}
		if (root->right != NULL) {
			enqueue(queue, (int)root->right);
		}
	}
}
